#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
struct edge{
    int a;
    int b;
    int x;
};
bool cmp(edge x,edge y){
    return x.x<y.x;
}
 int n,m;
ll ans=0xffffffff;
int bj[20];
edge a[1005];
int kj[20][20];
int bj1[20];
void dfs(int dq,int cnt){
    if(cnt==n){
        for(int i=1;i<=n;i++){
            int sum=0;
            memset(bj1,0,sizeof(bj1));
            queue<int>q;
            q.push(i);
            bj1[i]=-1;
            int bj2=0;
            while(!q.empty()){
                if(bj2)break;
                int f=q.front();
                q.pop();
                for(int j=1;j<=n;j++){
                    if(kj[f][j]&&!bj1[j]){
                       if(bj1[f]>0){
                         bj1[j]=bj1[f]+1;
                        sum+=bj1[j]*kj[f][j];
                        if(sum>ans){
                            bj2=1;
                            break;
                        }
                        q.push(j);
                       }
                       if(bj1[f]<0){
                         bj1[j]=1;
                        sum+=bj1[j]*kj[f][j];
                        if(sum>ans){
                            bj2=1;
                            break;
                        }
                        q.push(j);
                       }
                    }
                }
            }
            if(ans>sum)ans=sum;
        }
        return;
    }
    for(int i=dq;i<=m;i++){
        if(!bj[a[i].a]&&bj[a[i].b]){
            bj[a[i].a]=1;
            kj[a[i].a][a[i].b]= kj[a[i].b][a[i].a]=a[i].x;
            if(ans>a[i].x)dfs(dq+1,cnt+1);
            bj[a[i].a]=0;
            kj[a[i].a][a[i].b]= kj[a[i].b][a[i].a]=0;
        }
          if(bj[a[i].a]&&!bj[a[i].b]){
            bj[a[i].b]=1;
            kj[a[i].a][a[i].b]= kj[a[i].b][a[i].a]=a[i].x;
            if(ans>a[i].x)dfs(dq+1,cnt+1);
            bj[a[i].b]=0;
            kj[a[i].a][a[i].b]= kj[a[i].b][a[i].a]=0;
        }
          if(!bj[a[i].a]&&!bj[a[i].b]){
            bj[a[i].b]=1;
            bj[a[i].a]=1;
            kj[a[i].a][a[i].b]= kj[a[i].b][a[i].a]=a[i].x;
            if(ans>a[i].x)dfs(dq+1,cnt+1);
            bj[a[i].b]=0;
            bj[a[i].a]=0;
            kj[a[i].a][a[i].b]= kj[a[i].b][a[i].a]=0;
        }
    }
}
int main(){
   
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d %d %d",&a[i].a,&a[i].b,&a[i].x);
    }
    sort(a+1,a+1+m,cmp);
    dfs(1,1);
    cout<<ans;
    return 0;
}